# 来源：https://www.cnblogs.com/wushaogui/p/9239735.html#1117%E5%BC%97%E6%B4%9B%E4%BC%8A%E5%BE%B7%E7%AE%97%E6%B3%95floyd-warshall
# 使用Floyd算法找到所有对最短路径长度。
import networkx as nx
import matplotlib.pyplot as plt

G = nx.DiGraph()
G.add_weighted_edges_from([('0', '3', 3), ('0', '1', -5), ('0', '2', 2), ('1', '2', 4), ('2', '3', 1)])

# 边和节点信息
edge_labels = nx.get_edge_attributes(G, 'weight')
labels = {'0': '0', '1': '1', '2': '2', '3': '3'}

# 生成节点位置
pos = nx.spring_layout(G)

# 把节点画出来
nx.draw_networkx_nodes(G, pos, node_color='g', node_size=500, alpha=0.8)

# 把边画出来
nx.draw_networkx_edges(G, pos, width=1.0, alpha=0.5, edge_color='b')

# 把节点的标签画出来
nx.draw_networkx_labels(G, pos, labels, font_size=16)

# 把边权重画出来
nx.draw_networkx_edge_labels(G, pos, edge_labels)

# 显示graph
plt.title('有权图')
plt.axis('on')
plt.xticks([])
plt.yticks([])
plt.show()

# 计算最短路径长度
lenght = nx.floyd_warshall(G, weight='weight')

# 计算最短路径上的前驱与路径长度
predecessor, distance1 = nx.floyd_warshall_predecessor_and_distance(G, weight='weight')

# 计算两两节点之间的最短距离,并以numpy矩阵形式返回
distance2 = nx.floyd_warshall_numpy(G, weight='weight')

print(list(lenght))
print(predecessor)
print(list(distance1))
print(distance2)
